package codetop.dp;

public class Code044 {
    public boolean isMatch(String s, String p) {
        int m=s.length();
        int n=p.length();
        boolean dp[][]=new boolean[m+1][n+1];
        dp[0][0]=true;
        for (int i = 1; i < n+1; i++) {
            if (p.charAt(i-1)=='*')dp[0][i]=true;
            else break;
        }
        for (int i = 1; i <m+1 ; i++) {
            for (int j = 1; j < n+1; j++) {
                char c1=s.charAt(i-1);
                char c2=p.charAt(j-1);
                if (c2=='?'||c1==c2){
                    dp[i][j]=dp[i-1][j-1];
                }else if (c2=='*'){
                    dp[i][j]=dp[i-1][j]||dp[i][j-1];
                }else {
                    dp[i][j]=false;
                }
            }
        }
        return dp[m][n];
    }
}
